A network device such as a router typically includes a switch fabric that is configurable to direct packets received at particular device inputs to particular device outputs. The switch fabric may be implemented as a load-balanced switch fabric, in which multiple parallel paths through the switch fabric are provided in order to increase its throughput capacity for a given operating rate.
In a typical conventional arrangement, input packets are separated into cells that traverse respective paths through the switch fabric and are then reassembled into output packets. However, the multiple parallel paths of the switch fabric often have different delays, possibly due to factors such as differences in queue occupancies in these paths. Accordingly, cells from the same input packet or input packet stream may experience different delays as they traverse different paths through the switch fabric. The cells can therefore arrive at switch fabric outputs in a different order than that in which they were applied to switch fabric inputs, thereby significantly complicating the reassembly of cells into output packets. This difficulty associated with load-balanced switch fabrics is commonly referred to as the cell reordering problem.
Various techniques are known in the art for addressing the cell reordering problem. Some of these techniques impose constraints on how the cells can be sent through the switch fabric. For example, one such technique requires that cells be sent through the switch fabric in uniform frames. Unfortunately, this technique can introduce significant delays in routing the cells through the switch fabric, due to the additional time required to fill the frames uniformly with cells. Also, this technique and other constraint-imposing techniques not only introduce significant delays, but also unduly restrict the configuration of the switch fabric itself. Configuration restrictions of this type can make it much more difficult for the switch fabric to accommodate other common router throughput requirements, such as multicast traffic and multiple levels of cell priority.